package solution;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution {
    class TreeNode {
        int val;
        TreeNode right;
        TreeNode left;

        public TreeNode(int val) {
            this.val = val;
        }

        public TreeNode() {
        }
    }

    TreeNode root;

    public boolean isChildSymmetric(TreeNode leftTree, TreeNode rightTree) {
        //上一个结点的左右子树都为空：true
        if (leftTree == null || rightTree == null) {
            if (leftTree == rightTree)
                return true;
            return false;
        }
        //值相等：继续往下判断
        else if (leftTree.val == rightTree.val) {
            return isChildSymmetric(leftTree.left, rightTree.right) && isChildSymmetric(leftTree.right, rightTree.left);
        } else
            return false;
    }

    public boolean isSymmetric(TreeNode root) {
        //root为空：true
        if (root == null)
            return true;
        else
            return isChildSymmetric(root.left, root.right);
    }

    public void levelOrder (TreeNode root) {
        if(root == null)
            return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        TreeNode curNode = new TreeNode();
        while (!queue.isEmpty()) {
            //每一次循环curNode的值都会改变 十分巧妙
            curNode = queue.poll();
            System.out.println(curNode.val);
            if (curNode.left != null) {
                queue.offer(curNode.left);
            }
            if (curNode.right != null) {
                queue.offer(curNode.right);
            }
        }
    }

    public List<List<Integer>> levelOrderRetrun (TreeNode root) {
        if (root == null) return null;
        List<List<Integer>> ret = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        TreeNode curNode = root;
        int levelSize = 0;
        while (!queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            levelSize = queue.size();
            while (levelSize != 0) {
                curNode = queue.poll();
                list.add(curNode.val);
                if (curNode.left != null) {
                    queue.offer(curNode.left);
                }
                if (curNode.right != null) {
                    queue.offer(curNode.right);
                }
                levelSize--;
            }
            ret.add(list);
        }
        return ret;
    }

    public boolean isComplete (TreeNode root) {
        if (root == null)
            return false;
        TreeNode curNode = new TreeNode();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(curNode);
        while (!queue.isEmpty()) {
            curNode = queue.poll();
            if (curNode != null) {
                queue.offer(curNode.left);
                queue.offer(curNode.right);
            } else {
                break;
            }
        }
        while (!queue.isEmpty()) {
            if (queue.poll() != null) {
                return false;
            }
        }
        return true;
    }

    public void lowestCommonAncestor (TreeNode root) {
        
    }

    public void creatTree () {
        root = new TreeNode(1);
        root.right = new TreeNode(3);
        root.left = new TreeNode(2);
        root.right.left = new TreeNode(4);
    }

    public static void main1(String[] args) {
        Solution solution = new Solution();
        solution.creatTree();
        System.out.println(solution.isComplete(solution.root));
    }

}
